using System;
using System.Collections;
using System.IO;

namespace Algorithms.Graph
{
	/// <summary>
	/// Summary description for Class1.
	/// </summary>
	public interface IGraph
	{
		string Name
		{
			get;
			set;
		}

		IList GetVertices();

		IList GetEdges();

		int GetNumberOfVertices();

		int GetNumberOfEdges();

		IVertex GetVertex(int vertexIndex);

		IEdge GetEdge(IVertex end1, IVertex end2);

		void AddEdge(int i, int j, object weight);
	}

	public interface IVertex
	{
		string Name
		{
			set;
			get;
		}

		bool Visited
		{
			get;
			set;
		}
		
		IList GetEdges();

		IEdge AddEdge(IEdge edge);

		IEdge AddEdge(IVertex vertex);

		IEdge AddEdge(IVertex vertex, object weight);

		IVertex[] GetLinkedVertices();

		bool IsLinkedWith(IEdge edge);

		bool IsLinkedWith(IVertex v);

		int GetNumberOfEdges();
	}

	public interface IEdge
	{
		object Weight
		{
			get;
			set;
		}

		IVertex GetAnotherVertex(IVertex vertex);

		void SetLeftVertex(IVertex end);

		void SetRightVertex(IVertex end);
	}

	public abstract class AbstractVertex : IVertex
	{
		protected string name;

		protected bool visited;

		#region IVertex Members

		public string Name
		{
			get 
			{
				return name;
			}
			set 
			{
				name = value;
			}
		}

		public bool Visited
		{
			get
			{
				return visited;
			}
			set 
			{
				visited = value;
			}
		}

		public abstract IEdge AddEdge(IEdge edge);

		public abstract IList GetEdges();

		public abstract bool IsLinkedWith(IEdge edge);

		public abstract bool IsLinkedWith(IVertex v);

		public abstract IVertex[] GetLinkedVertices();

		public abstract IEdge AddEdge(IVertex vertex);

		public abstract IEdge AddEdge(IVertex vertex, object weight);

		public abstract int GetNumberOfEdges();

		#endregion

	}

	namespace Dense
	{
		public class Vertex : AbstractVertex
		{
			protected IList edges;

			public Vertex()
			{
				visited = false;
				edges = new ArrayList();
			}

			public Vertex(string name)
			{
				visited = false;
				edges = new ArrayList();
				this.name = name;
			}

			#region IVertex Members

			public override IList GetEdges()
			{
				return edges;
			}

			public override IEdge AddEdge(IEdge edge)
			{
				if(!IsLinkedWith(edge))
				{
					edges.Add(edge);
				}
				return edge;
			}

			public override IEdge AddEdge(IVertex vertex)
			{
				IEdge edge = null;
				if(! IsLinkedWith(vertex))
				{
					edge = new Edge(this, vertex);
					AddEdge(edge);
				}
				return edge;
			}
		
			public override IEdge AddEdge(IVertex vertex, object weight)
			{
				IEdge edge = null;
				if(! IsLinkedWith(vertex))
				{
					edge = new Edge(this, vertex, weight);
					AddEdge(edge);
				}
				return edge;
			}

			#endregion

			public override bool IsLinkedWith(IEdge edge)
			{
				foreach(IEdge e in edges)
				{
					if(e.Equals(edge))
					{
						return true;
					}
				}

				return true;
			}

			public override bool IsLinkedWith(IVertex vertex)
			{
				IList linkedVertices = GetLinkedVertices();
				foreach(IVertex v in linkedVertices)
				{
					if(v.Equals(vertex))
					{
						return true;
					}
				}

				return false;
			}

			public override int GetNumberOfEdges()
			{
				return this.edges.Count;
			}

			public override IVertex[] GetLinkedVertices()
			{
				IList linkedVertices = new ArrayList();
				IVertex[] vertices = null;

				foreach(IEdge edge in edges)
				{
					linkedVertices.Add(edge.GetAnotherVertex(this));
				}
				vertices = new IVertex[linkedVertices.Count];

				linkedVertices.CopyTo(vertices, linkedVertices.Count);
				return vertices;
			}
		}

		public class Edge : IEdge
		{
			protected object weight;

			protected IVertex[] vertices;

			public Edge()
			{

			}

			public Edge(IVertex e1, IVertex e2)
			{
				vertices = new Vertex[2];
				vertices[0] = e1;
				vertices[1] = e2;
			}

			public Edge(IVertex e1, IVertex e2, object weight)
			{
				vertices = new Vertex[2];
				vertices[0] = e1;
				vertices[1] = e2;
				this.weight = weight;
			}

			#region IEdge Members

			public object Weight
			{
				get 
				{
					return weight;
				}
				set
				{
					weight = value;
				}
			}

			public IVertex GetAnotherVertex(IVertex vertex)
			{
				return vertices[0].Equals(vertex) ? vertices[1] : vertices[0];
			}

			public IVertex[] Vertices
			{
				get 
				{
					return vertices;
				}
			}

			public void SetLeftVertex(IVertex v)
			{
				vertices[0] = v;
			}

			public void SetRightVertex(IVertex v)
			{
				vertices[1] = v;
			}

			#endregion
		}

		public class Graph : IGraph
		{
			protected string name;

			protected IList vertices;

			protected IList edges;

			#region IGraph Members

			public string Name
			{
				get
				{
					return name;

				}
				set
				{
					name = value;
				}
			}

			public IList GetVertices()
			{
				return vertices;
			}

			public IList GetEdges()
			{
				return edges;
			}

			public int GetNumberOfVertices()
			{
				return vertices.Count;
			}

			public int GetNumberOfEdges()
			{
				return edges.Count;
			}

			public IVertex GetVertex(int vertexIndex)
			{
				return (IVertex) vertices[vertexIndex];
			}

			public void AddEdge(IVertex u, IVertex v, object weight)
			{
				IEdge edge = u.AddEdge(v, weight);
				this.edges.Add(edge);
			}

			public void AddEdge(int i, int j, object weight)
			{
				IEdge edge = new Edge();
				edge.Weight = weight;

				IVertex end1 = GetVertex(i);
				IVertex end2 = GetVertex(j);
				edge.SetLeftVertex(end1);
				edge.SetRightVertex(end2);
				end1.AddEdge(edge);
				end2.AddEdge(edge);
			}

			public IEdge GetEdge(IVertex end1, IVertex end2)
			{
				foreach(IEdge edge in end1.GetEdges())
				{
					IVertex v = edge.GetAnotherVertex(end1);
					if(v.Equals(end2))
					{
						return edge;
					}
				}

				return null;
			}

			#endregion

		}
	}

	
}
